The present invention relates generally to the generation of images with output devices such as printers and computer monitors, and more particularly to a method and apparatus for rendering an image from an outline representation and a description of the characteristics of the image.
A computer system can be used to create and output images on a wide variety of output devices. Raster devices, such as video displays, laser printers, and color plotters, as well as other devices such as typesetters and image setters, are popular for outputting 2-dimensional images.
The process of rendering an image for display by an output device can be complex. A raster pixel map, comprising a matrix of individual pixels, can represent an image and a raster output device can use the pixel map to create a permanent or semi-permanent depiction of the image. For example, a laser printer can print dots on a piece of paper corresponding to the information of the pixel map. Alternatively, a computer monitor can illuminate pixels based upon the information of the pixel map. The depicted image typically contains a number of predefined shapes, such as characters, which can be described as bit maps. These bit maps can be used to create the pixel map of the image.
A problem with storing predefined shapes as bit maps on computer systems is that they can consume a great deal of memory space. For a character of a font, for example, a different bit map is required for each font size, orientation, stem weight, etc., even though the bit maps all have the same general appearance. In order to conserve limited memory space when printing characters, and to enhance the flexibility of character displays, shape descriptions employing Bezier curves and "hints" have been developed to describe text characters in less memory space than would be required for storing a collection of bit maps of these characters.
For example, a popular character outline format developed by Adobe Systems, Inc., ("Adobe") of Mountain View, Calif. is the Type 1.RTM. font format, which is a subset of the PostScript.RTM. language, also developed by Adobe. The PostScript Interpreter (a computer program that processes programs written in the PostScript language) operates to render bit maps from character outlines and other character information. For example, the PostScript Interpreter can generate a bit mapped character having designated size, orientation, and other characteristics. A bit map is generated which approximates a specified character outline, and the bit map is then used to create an image on a raster output device. "Hints" are typically used to adjust the outlines to improve the final alignment and appearance of the bit map image.
U.S. Pat. No. 5,301,267 of Hassett et al. teaches a control device for interpreting shape definitions and for converting the outlines and hints provided therefrom to rasterized bit maps of characters which can be stored or displayed on raster devices. The control device can transform a character's outline data from a character coordinate space to a device coordinate space which allows the character to be displayed. A character is first converted from its Type 1 format to a stream of hinted, scaled, and transformed Bezier control points. The Bezier control points are used to define the curves and lines included in the transformed character. A Bezier stack machine recursively subdivides the Bezier curves. Each curve is subdivided into two pieces unless it passes a flatness test and can be approximated as a straight line segment. A digital differential analyzer processes line segments to determine where they cross pixel midlines, where the pixels define an output resolution. Information about these crossings is used to fill specific pixels and create a bit map image of the original outline character.
A problem associated with processing Bezier curves involves the storage and retrieval of the curves to and from memory. Memory structures for storing data are known in the art. For example, Donald E. Knuth, in The Art of Computer Programming, Vol. 1, Addison Wesley, describes a double-ended queue memory structure. This memory structure can be used both as a queue (first-in first-out) or as a stack (last-in first-out) to write and read data from either end of the memory structure.
A problem encountered with prior art processes, such as the method disclosed by Hassett et al., is that the recursive subdivision process used on Bezier curves can result in somewhat inaccurate cross specifications. This occurs because, in these processes, a Bezier curve is approximated by a series of straight line segments, which can cause inaccurate cross placements.
Another problem with prior art processes is that they typically use different methods for processing Bezier curves and straight line segments, and can thus prove inefficient in terms of hardware requirements.
A universal problem encountered with prior art processes is how to efficiently determine when to stop subdividing the Bezier curves. If the subdivision is stopped too soon, poor results may occur. If the subdivision is allowed to go too far, processing speed suffers.